//
//  206. 反转链表.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/22.
//

import Foundation

//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//
//
//示例 1：
//
//
//输入：head = [1,2,3,4,5]
//输出：[5,4,3,2,1]
//示例 2：
//
//
//输入：head = [1,2]
//输出：[2,1]
//示例 3：
//
//输入：head = []
//输出：[]
//
//
//提示：
//
//链表中节点的数目范围是 [0, 5000]
//-5000 <= Node.val <= 5000
//
//
//进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

//思路
//
//3个指针遍历列表，遍历的同时，反转每个节点的next指针指向其前节点。
//
//算法
//
//定义3个指针： prev，cur和next。prev在cur的前面，next在cur的后面。
//
//将cur.next暂存为next；
//每次让cur.next指向prev，实现一次局部反转；
//cur和prev同时往后移动一个位置，即prev移到cur，cur移到next；
//循环上述过程，直至cur到达链表尾部；
//

func reverseList(_ head: ListNode?) -> ListNode? {
    var prev: ListNode?
    var cur = head
    while let theCur = cur {
        let next = theCur.next
        theCur.next = prev
        prev = theCur
        cur = next
    }
    return prev
}

func reverseList1(_ head: ListNode?) -> ListNode? {
    var prev: ListNode?
    var cur = head
    while let theCur = cur {
        let next = theCur.next
        theCur.next =  prev
        prev = theCur
        cur = next
    }
    return prev
}


